ν¬μ€νΈμ κ΄λ ¨λ λͺ¨λ μ½λλ€μ μ°Έκ³ URLμμ νμΈν μ μμ΅λλ€.
π§· HashMap
Java Collections Frameworkμ μν ꡬν체 ν΄λμ€μ΄λ€.
πͺ HashMapκ³Ό HashTable
μ΄ λμ Javaμ API μ΄λ¦μ΄λ€. HashTable λν Map μΈν°νμ΄μ€λ₯Ό ꡬννκ³ μμ΄ HashMap κ³Ό μ 곡νλ κΈ°λ₯μ κ°λ€.
- νμ§λ§
HashMapμ 보쑰 ν΄μ ν¨μ(2μ°¨ ν΄μ ν¨μ)λ₯Ό μ¬μ©νμ¬ λ³΄μ‘° ν΄μ ν¨μλ₯Ό μ¬μ©νμ§ μλHashTableμ λΉν΄ ν΄μ μΆ©λμ΄ λ λ°μν μ μμ΄ μλμ μΈ μ±λ₯μ μ΄μ μ΄ μλ€. - λν,
HashTableꡬνμ κ±°μ λ³νκ° μμ§λ§,HashMapμ μ§μμ μΌλ‘ κ°μ λκ³ μλ€.
HashTableμ JDK 1.0λΆν° μλ APIμ΄κ³ , HashMapμ Java 2μμ μ²μ μ λ³΄μΈ Java Collections Frameworkμ μν APIλ€.
μ΄ λμ μ μνλ€λ©΄, "ν€μ λν ν΄μ κ°μ μ¬μ©νμ¬ κ°μ μ μ₯νκ³ μ‘°ννλ©°, ν€-κ° μμ κ°μμ λ°λΌ λμ μΌλ‘ ν¬κΈ°κ° μ¦κ°νλ associate array"λΌκ³ ν μ μλ€.
mapμ μλ λμ κ΄κ³λ₯Ό μ§μΉνλ μ©μ΄λ‘,HashMapμ ν€ μ§ν©μΈ μ μμκ³Ό κ° μ§ν©μΈ 곡μμ λμμ ν΄μ ν¨μλ₯Ό μ΄μ©νλ€.
associate arrayλ₯Ό μ§μΉνλ λ€λ₯Έ μ©μ΄λ‘λ
Map,Dictionary,Symbol Tableλ±μ΄ μλ€.
μ΄ λμ μ μΈλΆλ₯Ό 보면, associate arrayλ₯Ό μ§μΉνκΈ° μν΄ HashTable μ Dictionary λΌλ μ΄λ¦μ μ¬μ©νκ³ , HashMap μ μ΄λ¦ κ·Έλλ‘ Map μ΄λΌλ μ©μ΄λ₯Ό μ¬μ©νλ€.
public class 8ccce55530bc3477c678dd9921b60f3e.gifHashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable { ... }
public class 928b3cc3fe40d69cd06cbe7f5f3767f8.gifHashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { ... }
πͺ ν΄μ λΆν¬μ ν΄μ μΆ©λ
λμΌνμ§ μμ μ΄λ€ κ°μ²΄ Xμ Yκ° μμ λ, X.equals(Y) κ° κ±°μ§μΌ λ X.hashCode() != Y.hashCode() μ΄λΌλ©΄, μ΄λ μ¬μ©νλ ν΄μ ν¨μλ μμ ν ν΄μ ν¨μλΌκ³ νλ€.
Boolean κ°μ΄ μλ‘ κ΅¬λ³λλ κ°μ²΄μ μ’
λ₯κ° μ κ±°λ, Integer , Long , Double κ°μ Number κ°μ²΄λ κ°μ²΄κ° λνλ΄λ €λ κ° μ체λ₯Ό ν΄μ κ°μΌλ‘ μ¬μ©ν μ μκΈ° λλ¬Έμ μμ ν ν΄μ ν¨μ λμμΌλ‘ μΌμ μ μλ€.
- νμ§λ§
Stringμ΄λPOJO(Plain Old Java Object)μ λνμ¬ μμ ν ν΄μ ν¨μλ₯Ό μ μνλ κ²μ μ¬μ€μ λΆκ°λ₯νλ€.
POJO(Plain Old Java Object) π«
λ§ κ·Έλλ‘ μ€λλ λ°©μμ κ°λ¨ν μλ° κ°μ²΄λΌλ λ§λ‘, μ€λ νλ μμν¬λ€μ μ¬μ©νκ² λλ©΄μ ν΄λΉ νλ μμν¬μ μ’ μλ "무거μ΄" κ°μ²΄λ₯Ό λ§λ€κ² λ κ²μ λ°λ°ν΄μ μ¬μ©νκ² λ μ©μ΄μ΄λ€.
- ν΄λΉ μ©μ΄λ μ΄ν νΉμ μλ° λͺ¨λΈμ΄λ κΈ°λ₯, νλ μμν¬ λ±μ λ°λ₯΄μ§ μμ μλ° κ°μ²΄λ₯Ό μ§μΉνλ λ§λ‘ μ¬μ©λμκ³ , λνμ μΌλ‘ μ€νλ§ νλ μμν¬κ° POJO λ°©μμ νλ μμν¬λ€.
- μ΄μμ μΌλ‘λ μλ° μΈμ΄ μ¬μ μΈμ μ΄λ ν μ νμλ λ¬Άμ΄μ§ μμ μλ° κ°μ²΄μ΄λ―λ‘, 미리 μ μλ ν΄λμ€μ νμ₯, 미리 μ μλ μΈν°νμ΄μ€μ ꡬν, 미리 μ μλ μ΄λ Έν μ΄μ μ ν¬ν¨νλ νλμ ν΄μλ μλλ€.
-
νμ§λ§, λλΆλΆ μ€μ μ μ λμμ μν΄ λ―Έλ¦¬ μ μλ μ΄λ Έν μ΄μ μ μ¬μ©μ μꡬνλ€.
μ μ μ°μ°λ§μΌλ‘ λΉ λ₯΄κ² λμν μ μλ μμ ν ν΄μ ν¨μκ° μλλΌλ, μ΄λ₯Ό HashMap μμ μ¬μ©ν μ μλ κ²μ μλλ€.
-
HashMapμ κΈ°λ³Έμ μΌλ‘ κ° κ°μ²΄μhashCode()κ° λ°ννλ κ°μ μ¬μ©νκ³ , κ²°κ³Όμ μλ£νμintλ€. κ·Έλ¦¬κ³ 32λΉνΈ μ μ μλ£νμΌλ‘λ μμ μλ£ ν΄μ ν¨μλ₯Ό λ§λ€ μ μλ€.- λ Όλ¦¬μ μΌλ‘, μμ± κ°λ₯ν κ°μ²΄μ μκ° λ³΄λ€ λ§μ μ μκ³
- λͺ¨λ
HashMapκ°μ²΄μμ μ 보μ₯νκΈ° μν΄ μμ μ κ·Όμ΄ κ°λ₯νκ² νλ €λ©΄ μμκ° μΈ λ°°μ΄μ λͺ¨λHashMapμ΄ κ°μ§κ³ μμ΄μΌ νκΈ° λλ¬Έμ΄λ€.
λ°λΌμ HashMap μ λΉλ‘―ν λ§μ ν΄μ ν¨μλ₯Ό μ΄μ©νλ associate array ꡬν체μμλ λ©λͺ¨λ¦¬λ₯Ό μ μ½νκΈ° μν΄ μ€μ ν΄μ ν¨μμ νν μ μ λ²μ λ³΄λ€ μμ Mκ°μ μμκ° μλ λ°°μ΄λ§μ μ¬μ©νλ€.
- κ·Έλ¦¬κ³ κ°μ²΄μ λν ν΄μ μ½λμ λλ¨Έμ§ κ°μ ν΄μ λ²ν· μΈλ±μ€ κ°μΌλ‘ μ¬μ©νλ€.
int index = X.hashCode() % M;
μ΄λ¬ν λ°©μμ, μλ‘ λ€λ₯Έ ν΄μ μ½λλ₯Ό κ°μ§λ μλ‘ λ€λ₯Έ κ°μ²΄κ° 1/Mμ νλ₯ λ‘ κ°μ ν΄μ λ²ν·μ μ¬μ©νκ² λλ€.
-
μ΄λ λ λ€λ₯Έ μ’ λ₯μ ν΄μ μΆ©λμ΄κ³ , μ΄λ₯Ό ν΄κ²°νκΈ° μν΄ ν€-κ° μ λ°μ΄ν°λ₯Ό μ μ μ₯νκ³ μ‘°νν μ μκ² νλ λ°©μμ μλ 2κ°μ§κ° μλ€. μλ λ λ°©μμ λν μ€λͺ μ POSTμμ νμΈν μ μλ€.
- Open Addressing
- Separate Chaining
πͺ Java 8 HashMapμμμ Separate Chaining
Java HashMap μμ μ¬μ©νλ λ°©μμ Separate Chainingμ΄λ€. κ·Έλ¦¬κ³ μμμ μΈκΈνλ―, HashMap μ μ§μμ μΌλ‘ κ°μ λκ³ μλ€.
- Java 2 ~ 7κΉμ§λ μ½λλ λ¬λΌλ ꡬν μκ³ λ¦¬μ¦ μ체λ κ°μκ³ , ν΄μ ν¨μμ κ°μ΄ κ· λ± λΆν¬ μνλΌλ κ°μ νμ,
get()μ νΈμΆ κΈ°λκ°μ μ΄λ€. - νμ§λ§ Java 8μμλ μ΄μ κΉμ§ μ¬μ©νλ μ°κ²° 리μ€νΈ λ°©μμμ νΈλ¦¬ λ°©μμΌλ‘ λ³κ²½νμ¬, νΈμΆ κΈ°λκ°μ΄ μ 보μ₯νμ¬ μ±λ₯μμ μ΄μ μ΄ μλ€.
μ°κ²° 리μ€νΈλ₯Ό μ¬μ©ν κ²μΈκ°, νΈλ¦¬λ₯Ό μ¬μ©ν κ²μΈκ°λ₯Ό κ²°μ νλ μμΈμ νλμ ν΄μ λ²ν·μ ν λΉλ ν€-κ° μμ κ°μμ΄κ³ , μ΄ λν POSTμμ λ€λ£¨μλ€.
Java 8 HashMap μ Entry ν΄λμ€ λμ Node ν΄λμ€λ₯Ό μ¬μ©νλ€. μ΄ ν΄λμ€μλ Java 7 HashMap κ³Ό λ¬λ¦¬ νΈλ¦¬λ₯Ό μ¬μ©ν μ μλλ‘ νμ ν΄λμ€μ TreeNode λ₯Ό ν¬ν¨νκ³ μλ€.
- μ΄λ
Red-Black Treeλ₯Ό μ¬μ©νκ³ , νΈλ¦¬ μν μ μ¬μ©νλ λμ νλ¨ κΈ°μ€μ ν΄μ ν¨μ κ°μ΄λ€.
πͺ ν΄μ λ²ν· λμ νμ₯
ν΄μ λ²ν·μ κ°μκ° μ λ€λ©΄, λ©λͺ¨λ¦¬ μ¬μ©μ μλ μ μμ§λ§ ν΄μ μΆ©λλ‘ μΈν΄ μ±λ₯μ μμ€μ΄ λ°μνλ€.
- λ°λΌμ
HashMapμ μΌμ κ°μ μ΄μμ λ°μ΄ν°κ° μλ€λ©΄, ν΄μ λ²ν·μ κ°μλ₯Ό 2λ°°λ‘ λλ¦°λ€. - ν΄μ λ²ν·μ κ°μλ₯Ό λλ¦ΌμΌλ‘μ¨, κ°λ μμμ Έ ν΄μ μΆ©λλ‘ μΈν μ±λ₯ μμ€ λ¬Έμ λ₯Ό μ΄λ μ λ ν΄κ²°ν μ μλ€.
ν΄μ λ²ν·μ κ°μμ κΈ°λ³Έκ°μ 16 μ΄κ³ , μκ³μ μ μ΄λ₯Ό λλ§λ€ λ λ°°μ© μ¦κ°μν¨λ€.
- λ²ν·μ μ΅λ κ°μλ κ°λ€.
- μκ³μ μ νμ¬μ λ°μ΄ν° κ°μκ° "load factor * νμ¬μ ν΄μ λ²ν· κ°μ"μ μ΄λ₯Ό λμ΄λ€. (
load factorλ 0.75, μ¦ 3/4μ΄λ€.)
νμ§λ§ λ λ°°λ‘ μ¦κ°ν λλ§λ€, λͺ¨λ ν€-κ° μμ μ½μ΄ μλ‘μ΄ Separate Chainingμ ꡬμ±ν΄μΌ νλ λ¬Έμ κ° λ°μνλ€.
HashMapμμ±μμ μΈμλ‘ μ΄κΈ° ν΄μ λ²ν· κ°μλ₯Ό μ§μ ν μ μμΌλ―λ‘, ν΄λΉHashMapκ°μ²΄μ μ μ₯λ λ°μ΄ν°μ κ°μκ° μ΄λ μ λμΈμ§ μμΈ‘ κ°λ₯ν κ²½μ°μλ μ΄λ₯Ό μμ±μμ μΈμλ‘ μ§μ νλ©΄ λΆνμν Separate Chainingμ μ¬κ΅¬μ±μ νΌν μ μλ€.
λλ€λ₯Έ λ¬Έμ λ‘, ν΄μ λ²ν·μ κ°μ mμ΄ ννκ° λκΈ°μ, index = X.hashCode() % M κ³μ° μ X.hashCode() μ νμ aκ°μ λΉνΈλ§ μ¬μ©νκ² λλ€.
- μ¦ ν΄μ ν¨μκ° 32λΉνΈ μμμ κ³ λ₯΄κ² μ¬μ©νλλ‘ λ§λ€μλλΌλ ν΄μ κ°μ 2μ μΉμλ‘ λλλ©΄ ν΄μ μΆ©λμ΄ μ½κ² λ°μν μ μλ€.
λ°λΌμ 보쑰 ν΄μ ν¨μκ° νμνλ€.
πͺ 보쑰 ν΄μ ν¨μ
index = X.hashCode() % M κ³μ° μμλ Mμ΄ μμμΌ λ index κ°μ λΆν¬κ° κ°μ₯ κ· λ±ν μ μλ€.
- νμ§λ§ μμκ° μλκΈ° λλ¬Έμ λ³λμ 보쑰 ν΄μ ν¨μλ₯Ό μ¬μ©νμ¬ κ· λ± λΆν¬λ₯Ό λλλ€.
보쑰 ν΄μ ν¨μμ λͺ©μ μ 'ν€'μ ν΄μ κ°μ λ³ννμ¬, ν΄μ μΆ©λ κ°λ₯μ±μ μ€μ΄λ κ²μ΄λ€.
- Java 5 ~ 7κΉμ§λ λμΌν λ°©μμ 보쑰 ν΄μ ν¨μλ₯Ό μ¬μ©νλλ°, Java 8λΆν°λ μ’ λ λ¨μν ννλ‘ λ³κ²½λμλ€.
-
λ¨μνκ² μμ 16λΉνΈ κ°μ XOR μ°μ°νλ λ°©μμΌλ‘ λ³κ²½λμλλ°, μλ 2κ°μ§ μ΄μ κ° μλ€.
- Java 8μμλ ν΄μ μΆ©λμ΄ λ§μ΄ λ°μνλ©΄ μ°κ²° 리μ€νΈ λμ νΈλ¦¬λ₯Ό μ¬μ©ν¨μΌλ‘μ¨ μ±λ₯ λ¬Έμ λ₯Ό λ§μ΄ μννκΈ° λλ¬Έμ΄λ€.
- μ΅κ·Όμ ν΄μ ν¨μλ κ· λ± λΆν¬λ₯Ό μ λ§λλ κ²½ν₯μ΄ μμ΄ λ³΄μ‘° ν΄μ ν¨μμ ν¨κ³Όκ° ν¬μ§ μκΈ° λλ¬Έμ΄λ€.
πͺ String κ°μ²΄μ λν ν΄μ ν¨μ
String κ°μ²΄μ λν ν΄μ ν¨μ μν μκ°μ λ¬Έμμ΄ κΈΈμ΄μ λΉλ‘νλ€.
- JDK 1.1μμλ λ λΉ λ₯Έ ν΄μ ν¨μ μνμ μν΄ μΌμ κ°κ²©μ λ¬Έμμ λν ν΄μλ₯Ό λμ ν κ°μ Stringμ λν ν΄μ ν¨μλ‘ μ¬μ©νλ€.
νμ§λ§ μ΄λ¬ν λ°©μμ λ€μκ³Ό κ°μ λ¬Έμ λ₯Ό μΌκΈ°νλ€.
- μΉμμ URLμ κΈΈμ΄κ° μμ κΈμμ μ΄λ₯΄λ©΄μ μ λΆλΆμ λμΌνκ² κ΅¬μ±λλ κ²½μ°κ° λ§λ€.
- μ΄ κ²½μ° μλ‘ λ€λ₯Έ URLμ ν΄μ κ°μ΄ κ°μμ§λ λΉλκ° λ§€μ° λμμ§ μ μλ€.
λ°λΌμ Horner's methodλ₯Ό ꡬνν λ°©μμ μ¬μ©νκ³ μλ€.
String κ°μ²΄ ν΄μ ν¨μμμ 31μ μ¬μ©νλλ°,
-
31μ μμμ΄λ©°, μ΄λ€ μμ 31μ κ³±νλ κ²μ λΉ λ₯΄κ² κ³μ°ν μ μλ€.
31N = 32N - N = (N << 5) - N
- μ¦, μ±λ₯ ν₯μμ λλͺ¨νλ€!